By way of introduction, the process of hiding or embedding information in a computer-aided fashion in a video, audio or any suitable media item generally comes under the overall category of watermarking. The watermarking process is typically called “digital watermarking” when the embedded data identifies the media-item itself or the content-owner, and sometimes known as “forensic fingerprinting” when the embedded data identifies the consumer of the media-item. In forensic fingerprinting, if a user were to leak some piece of content, his/her identity (ID) could be traced using information hidden in the content. A common watermarking requirement is to make the leaker detection/identification process as efficient as possible, so that even a small fragment (“window”) of the media-item would allow traitor tracing (identifying an illegitimate distributor (traitor) of the media item).